题目大意
在一个平面上有n个点，求一条直线最多能够经过多少个这些点。
解题思路
哈希表保存斜率
代码
注意有个坑：
测试集[[0,0],[94911151,94911150],[94911152,94911151]]，由于数字大，直接内置除法斜率会算成一样的，用numpy库运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import numpy as np
class Solution:
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
n = len(points)
slope_map = {}
result = 0
for i in range(n):
# print(slope_map)
slope_map.clear()
same, vertical = 1, 0
slope_max = 0
for j in range(i + 1, n):
dx, dy = points[i].x - points[j].x, points[i].y - points[j].y
if dx == dy == 0: # 同一个点
same += 1
elif dx == 0: # 斜率无限大，垂直
vertical += 1
else:
slope = (dy * np.longdouble(1)) / dx
# slope = float(dy) / float(dx)
# print(slope)
slope_map[slope] = slope_map.get(slope, 0) + 1
slope_max = max(slope_max, slope_map[slope])
result = max(result, max(slope_max, vertical) + same)
return result
|
总结